<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
<HEAD>
	<META HTTP-EQUIV="CONTENT-TYPE" CONTENT="text/html; charset=windows-1252">
	<TITLE></TITLE>
	<META NAME="GENERATOR" CONTENT="BrOffice.org 2.4  (Win32)">
	<META NAME="AUTHOR" CONTENT="Karina Kieling">
	<META NAME="CREATED" CONTENT="20081004;19181400">
	<META NAME="CHANGEDBY" CONTENT="Karina Kieling">
	<META NAME="CHANGED" CONTENT="20081101;22382653">
	<STYLE TYPE="text/css">
	<!--
		@page { margin: 2cm }
		P { margin-bottom: 0.21cm }
		P.western { so-language: pt-BR }
	-->
	</STYLE>
</HEAD>
<BODY LANG="pt-BR" DIR="LTR">
<P STYLE="margin-bottom: 0cm; line-height: 150%"></P>
<P STYLE="margin-bottom: 0cm; line-height: 150%"></P>
<P STYLE="margin-bottom: 0cm; line-height: 150%"><B>AUT&Ocirc;MATO
FINITO</B></P>
<P CLASS="western"><BR><BR>
</P>
<P CLASS="western" ALIGN=JUSTIFY STYLE="line-height: 150%">	Segundo
Gesser (2003) &ldquo;um aut&ocirc;mato finito trabalha lendo um
string de s&iacute;mbolos e alterando se estado interno de acordo com
o controle. Se ao terminar a string o estado atual for um estado
considerado final, o aut&ocirc;mato aceita a entrada, sen&atilde;o
rejeita&rdquo;. Aho, Sethi e Ullmann definem como um diagrama de
transi&ccedil;&atilde;o onde reconhece as <A HREF="expressoes_regulares.html">express&otilde;es
regulares</A> compiladas.</P>
<P CLASS="western" ALIGN=JUSTIFY STYLE="line-height: 150%">	Um
aut&ocirc;mato finito pode ser Determin&iacute;stico (AFD) onde
dependendo do estado corrente e dos <A HREF="conceitos%20basicos.html">s&iacute;mbolos</A>
lido, o sistema pode assumir um &uacute;nico estado bem determinado
(MENEZES, 2001).</P>
<P CLASS="western" ALIGN=JUSTIFY STYLE="line-height: 150%">	Defini-se
formalmente AFD, como sendo um sistema formal M = (K, <FONT FACE="Symbol, serif">&#61523;</FONT>,
<FONT FACE="Symbol, serif">&#61540;</FONT>, qo, F), onde:</P>
<P CLASS="western" STYLE="text-indent: 1cm">		K <FONT FACE="Wingdings">&#61664;</FONT>
&Eacute; um conjunto finito n&atilde;o vazio de <U><B>Estados</B></U>;</P>
<P CLASS="western" STYLE="text-indent: 1cm"><FONT FACE="Symbol, serif">		&#61523;</FONT>
<FONT FACE="Wingdings">&#61664;</FONT> &Eacute; um Alfabeto finito,
de entrada;</P>
<P CLASS="western" STYLE="text-indent: 1cm"><FONT FACE="Symbol, serif">		&#61540;</FONT>
<FONT FACE="Wingdings">&#61664;</FONT> <U><B>Fun&ccedil;&atilde;o de
Mapeamento</B></U><U> </U>(ou fun&ccedil;&atilde;o de transi&ccedil;&atilde;o)</P>
<P CLASS="western" STYLE="text-indent: 1cm">		definida em: <B>K x </B><FONT FACE="Symbol, serif"><B>&#61523;</B></FONT><B>
</B><FONT FACE="Wingdings"><B>&#61664;</B></FONT><B> K</B></P>
<P CLASS="western" STYLE="text-indent: 1cm">		qo <FONT FACE="Wingdings">&#61664;</FONT>
<FONT FACE="Symbol, serif">&#61646;</FONT> K, &eacute; o <U><B>Estado
Inicial</B></U></P>
<P CLASS="western" STYLE="text-indent: 1cm">		F <FONT FACE="Wingdings">&#61664;</FONT>
<FONT FACE="Symbol, serif">&#61645;</FONT> K, &eacute; o conjunto de
<U><B>Estados Finais</B></U></P>
<P CLASS="western" STYLE="line-height: 150%">	O aut&ocirc;mato finito
tamb&eacute;m pode ser do tipo n&atilde;o-determin&iacute;stico (AFN)
denota que um mais de uma transi&ccedil;&atilde;o para fora de um
estado pode ser poss&iacute;vel para o mesmo s&iacute;mbolos de
entrada (AHO; SETHI; ULLMANN, 1995).</P>
<P CLASS="western" STYLE="line-height: 150%">	Pode ser representar um
aut&ocirc;mato finito por um diagrama de transi&ccedil;&atilde;o, que
s&atilde;o grafo dirigidos e rotulados, os v&eacute;rtices
representam os estados e as arestas as transi&ccedil;&otilde;es, o
estado inicial possui uma seta que indica, e os finais possuem
c&iacute;rculos duplos (GESSER, 2003).</P>
<P CLASS="western" ALIGN=CENTER><IMG SRC="automato%20finito_html_m71659954.gif" NAME="Quadro9" ALT="Quadro9" WIDTH=403 HEIGHT=311></P>
<P CLASS="western" ALIGN=CENTER><BR><BR>
</P>
<P CLASS="western" ALIGN=LEFT STYLE="margin-bottom: 0cm"><IMG SRC="automato%20finito_html_m637a0871.gif" ALIGN=MIDDLE>
<A HREF="Indice.html">Voltar &Iacute;ndice</A></P>
<P CLASS="western" ALIGN=LEFT STYLE="margin-bottom: 0cm"><BR>
</P>
<P CLASS="western" ALIGN=LEFT STYLE="margin-bottom: 0cm"><BR>
</P>
<P CLASS="western" ALIGN=LEFT STYLE="margin-bottom: 0cm"><BR>
</P>
</BODY>
</HTML>